
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
int hIndex1(int* citations, int citationsSize) {
     int left = 0, right = citationsSize;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;

        int cnt = 0;
        for (int i = 0; i < citationsSize; i++) {
            if (citations[i] >= mid) cnt++;
        }

        if (cnt >= mid) left = mid;
        else right = mid - 1;
    }
    return left;
}


int cmpfunc(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int hIndex2(int* citations, int citationsSize) {
    qsort(citations, citationsSize, sizeof(int), cmpfunc);
    int n = citationsSize;
    // bug 修复，h 不能等于 0，否则数组越界异常
    for (int h = n; h > 0; h--) {
        if (citations[n - h] >= h) return h;
    }
    return 0;
}

int hIndex3(int* citations, int citationsSize) {
    qsort(citations, citationsSize, sizeof(int), cmpfunc);
    int n = citationsSize;
    int left = 0, right = n;
    while (left < right) {
        int h = left + (right - left + 1) / 2;
        if (citations[n - h] >= h) left = h;
        else right = h - 1;
    }
    return left;
}


int hIndex(int* citations, int citationsSize) {
    int n = citationsSize;
    int* counter = (int*) malloc(sizeof(int) * (n + 1));
    memset(counter, 0, sizeof(int) * (n + 1));
    for (int i = 0; i < n; i++) {
        if (citations[i] >= n) {
            counter[n]++;
        } else {
            counter[citations[i]]++;
        }
    }

    int total = 0;
    for (int h = n; h >= 0; h--) {
        total += counter[h];
        if (total >= h) return h;
    }

    return 0;
}